Search results for " injection and surjection"
showing 10 items of 12 documents
Symmetric and finitely symmetric polynomials on the spaces ℓ∞ and L∞[0,+∞)
2018
We consider on the space l∞ polynomials that are invariant regarding permutations of the sequence variable or regarding finite permutations. Accordingly, they are trivial or factor through c0. The analogous study, with analogous results, is carried out on L∞[0,+∞), replacing the permutations of N by measurable bijections of [0,+∞) that preserve the Lebesgue measure.
Statistics-preserving bijections between classical and cyclic permutations
2012
Recently, Elizalde (2011) [2] has presented a bijection between the set C"n"+"1 of cyclic permutations on {1,2,...,n+1} and the set of permutations on {1,2,...,n} that preserves the descent set of the first n entries and the set of weak excedances. In this paper, we construct a bijection from C"n"+"1 to S"n that preserves the weak excedance set and that transfers quasi-fixed points into fixed points and left-to-right maxima into themselves. This induces a bijection from the set D"n of derangements to the set C"n"+"1^q of cycles without quasi-fixed points that preserves the weak excedance set. Moreover, we exhibit a kind of discrete continuity between C"n"+"1 and S"n that preserves at each s…
On bijections vs. unary functions
1996
A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.
Lehmer code transforms and Mahonian statistics on permutations
2012
Abstract In 2000 Babson and Steingrimsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006. In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections…
Decomposable Measures and Measures of Information for Crisp and Fuzzy Sets
1983
Abstract There exist bijections between the decomposable informations of Kampe de Feriet and Forte (1967a) and the decomposable measures of Weber (1982). Using integrals for Archimedean decomposable operations, introduced by Weber (1982), informations and measures of this type are extended from crisp to fuzzy sets. For ∨-decomposable measures, Sugeno’s (1974) integral is used. For ∧-decomposable informations, Nguyen’s (1977) construction and a modification are discussed.
Restriction of odd degree characters and natural correspondences
2016
Let $q$ be an odd prime power, $n > 1$, and let $P$ denote a maximal parabolic subgroup of $GL_n(q)$ with Levi subgroup $GL_{n-1}(q) \times GL_1(q)$. We restrict the odd-degree irreducible characters of $GL_n(q)$ to $P$ to discover a natural correspondence of characters, both for $GL_n(q)$ and $SL_n(q)$. A similar result is established for certain finite groups with self-normalizing Sylow $p$-subgroups. We also construct a canonical bijection between the odd-degree irreducible characters of $S_n$ and those of $M$, where $M$ is any maximal subgroup of $S_n$ of odd index; as well as between the odd-degree irreducible characters of $G = GL_n(q)$ or $GU_n(q)$ with $q$ odd and those of $N_{G}…
Catalan words avoiding pairs of length three patterns
2021
Catalan words are particular growth-restricted words counted by the eponymous integer sequence. In this article we consider Catalan words avoiding a pair of patterns of length 3, pursuing the recent initiating work of the first and last authors and of S. Kirgizov where (among other things) the enumeration of Catalan words avoiding a patterns of length 3 is completed. More precisely, we explore systematically the structural properties of the sets of words under consideration and give enumerating results by means of recursive decomposition, constructive bijections or bivariate generating functions with respect to the length and descent number. Some of the obtained enumerating sequences are kn…
Coprime actions and correspondences of Brauer characters
2017
We prove several results giving substantial evidence in support of the conjectural existence of a Glauberman–Isaacs bijection for Brauer characters under a coprime action. We also discuss related bijections for the McKay conjecture.
Avoiding patterns in irreducible permutations
2016
We explore the classical pattern avoidance question in the case of irreducible permutations, <i>i.e.</i>, those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{13…
Transmission of Genetic Properties in Permutation Problems: Study of Lehmer Code and Inversion Table Encoding
2021
Solution encoding describes the way decision variables are represented. In the case of permutation problems, the classical encoding should ensure that there are no duplicates. During crossover operations, repairs may be carried out to correct or avoid repetitions. The use of indirect encoding aims to define bijections between the classical permutation and a different representation of the decision variables. These encodings are not sensitive to duplicates. However, they lead to a loss of genetic properties during crossbreeding. This paper proposes a study of the impact of this loss both in the space of decision variables and in that of fitness values. We consider two indirect encoding: the …